package leetcode_200;

import helpclass.TreeNode;

/**
 *@author 周杨
 *PathSum_112 判断一棵树有无从根节点到叶节点某条路径等于输入的某个值 
 *describe:用回溯 基本是先序遍历的方法  AC 99%
 *2018年5月20日 下午9:54:19
 */
public class PathSum_112 {
	
	public static void main(String[] args) {
		PathSum_112 test=new PathSum_112();
		TreeNode root=new TreeNode(5);
		root.left=new TreeNode(-2);
		root.right=new TreeNode(3);
		root.left.left=new TreeNode(8);
		root.left.right=new TreeNode(5);
		root.right.left=new TreeNode(1);
		root.right.right=new TreeNode(2);
		test.hasPathSum(root, 8);
	}
	private int sum;
	public boolean hasPathSum(TreeNode root, int sum) {
		if(root==null)
			return false;
        this.sum=sum;
        return help(root,0);
    }
	private boolean help(TreeNode root,int count) {
		if(root.left!=null) {
			if(help(root.left,count+root.val))
				return true;
		}
		if(root.right!=null)
			if(help(root.right,count+root.val))
				return true;
		if(root.left==null&&root.right==null)
			if(count+root.val==this.sum)
				return true;
		return false;
	}
	
}
